package practise;

public class IsSubtree {
    /**
     * 它是循环遍历
     * 每遍历一个root中的节点就判断一次（调用一次isSameTree）
     * 不相同再向内部遍历
     * @param root
     * @param subRoot
     * @return
     */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        //空树是任何数的子树
        if(subRoot == null) {
            return true;
        }
        //subRoot不是空，但是 root 为空
        if(root == null) {
            return false;
        }
        //跟当前树相同
        if(isSameTree(root, subRoot)) {
            return true;
        }
        //跟当前左子树相同
        if(isSubtree(root.left, subRoot)) {
            return true;
        }
        //跟当前右子树相同
        if(isSubtree(root.right, subRoot)) {
            return true;
        }
        return false;
    }
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //先判断他们是不是都为空
        if(p == null && q == null) {
            return true;
        }
        //说明其中一个为空 另一个不为空
        if(p == null || q == null) {
            return false;
        }
        //判断它们值是否相同
        if(p.val != q.val) {
            return false;
        }
        //此时已经当前节点已经判断完毕，只要判断左边与右边既可以
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}
